package offer

import (
	. "GoLeetcode/common"
)

/*
时间复杂度:O(N)
空间复杂度:O(1)

利用二叉搜索树性质
*/

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	var ans *TreeNode
	for root != nil {
		if root.Val > p.Val {
			ans = root
			root = root.Left
		} else {
			root = root.Right
		}
	}
	return ans
}

/*
时间复杂度:O(N)
空间复杂度:O(N) 递归调用栈最多N层


*/
func inorderSuccessor1(root *TreeNode, p *TreeNode) *TreeNode {
	var cur, ans *TreeNode
	var dfs func(node *TreeNode)
	// 中序遍历，pre指向当前遍历的节点，ans指向pre的下一个节点
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}
		dfs(node.Left)
		// 对于中序序列中第一个值(即最左边的那个节点),此时cur是为nil的(因为要到下一步才会对cur进行赋值)
		// 然后退回到上一层,此时cur记录的是中序序列第一个节点的值,而当前的node是中序序列第二个节点的值
		if cur == p {
			ans = node
		}
		// 这里由于是中序遍历,cur=node就是在遍历过程中记录中序序列当前遍历到的值
		cur = node
		dfs(node.Right)
	}
	dfs(root)
	return ans
}
